package 寻找数组的中心下标;

/**
 * 寻找数组的中心下标，可以出现在两端，可以出现多个中心下标，返回最小下标
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 9, 8, 2, 2, 3, 4, 2};
        int index = pivotIndex(arr);
        System.out.println("index = " + index);
        index = pivotIndex2(arr);
        System.out.println("index = " + index);
    }

    /**
     * 指针法
     */
    public static int pivotIndex2(int[] arr) {
        int total = 0;
        for (int v : arr) {
            total += v;
        }

        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            int v = arr[i];

            // 关键点：左边sum * 2 + 中心值 == total，即为中心下标
            if (sum * 2 + v == total) {
                return i;
            }

            sum += v;
        }

        return -1;
    }

    public static int pivotIndex(int[] arr) {
        /*
            1、求合
            2、从左到右遍历求左右和
         */

        int rightSum = 0;
        for (int v : arr) {
            rightSum += v;
        }

        int leftSum = 0;
        for (int i = 0; i < arr.length; i++) {
            int curr = arr[i];
            leftSum += arr[i];
            if (leftSum == rightSum) {
                return i;
            }

            rightSum -= curr;
        }
        return -1;
    }

}
